| class DYNAMIC_BUCKET_TABLE{E,BUCKET<$BUCKET{E,BUCKET}} |
|---|
| **** | Data structure used to implement a hash table. Per-Ake Larson; Communications of the ACM Vol.31 (1988) P.446-457 The directory/segment structure is changed in favor of a dymnamically changing array as storage area. |
| COMPARE{_} |
| H_SET{_} | SET{_} |
| attr n_inds: INT; |
|---|
| **** | Returns the number of elements (resp. indices) in the table. |
| bucket(i:INT): BUCKET |
|---|
| create: SAME |
|---|
| create_sized(initial_size:INT): SAME |
|---|
| **** | Creating a table with another minimal size. This might be useful to avoid shrinking of large table which might get very empty. |
| dbg: STR |
|---|
| **** | Returns an interal string representation of the hashtable. For debugging only. |
| map_copy: SAME |
|---|
| **** | Returns a copy of self with all properties set like self. |
| set_bucket(i:INT,l:BUCKET) |
|---|
| attr asize: INT; |
|---|
| **** | The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal. |
| attr asize: INT; |
|---|
| **** | The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal. |
| attr bound: INT; |
|---|
| **** | Upper bound for split_pos. Is always initial_size * 2.pow(doubles) |
| attr bound: INT; |
|---|
| **** | Upper bound for split_pos. Is always initial_size * 2.pow(doubles) |
| attr doubles: INT; |
|---|
| **** | Number of times the initial table size has been doubled. |
| attr doubles: INT; |
|---|
| **** | Number of times the initial table size has been doubled. |
| grow |
|---|
| **** | Increases the size of the array by one. The functions changing the size of the bucket table: They are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow) |
| hash(e:E): INT |
|---|
| **** | Returns the bucket to store e. This number will be generated from the hash-value and be normailzed through the actual size of the set. |
| shared lower_fill_ratio: FLT := 0.800; |
|---|
| shared lower_fill_ratio: FLT := 0.800; |
|---|
| attr minsize: INT; |
|---|
| **** | Lower bound for the store size. |
| attr minsize: INT; |
|---|
| **** | Lower bound for the store size. |
| attr n_inds: INT; |
|---|
| **** | Returns the number of elements (resp. indices) in the table. |
| shrink |
|---|
| **** | Decreases the size of the array by one. Resizes the storage area, if neccessary. |
| attr split_pos: INT; |
|---|
| **** | Position of the next bucket to split. |
| attr split_pos: INT; |
|---|
| **** | Position of the next bucket to split. |
| attr store: AREF{BUCKET}; |
|---|
| **** | Here is the data being stored. |
| attr store: AREF{BUCKET}; |
|---|
| **** | Here is the data being stored. |
| update_delete |
|---|
| **** | Checks the actual fill ratio of the set. Removes a bucket from the hash table if the ratio is low enough. |
| update_insert |
|---|
| **** | Checks the actual fill ratio of the set. Adds a bucket to the hash table if the ratio is high enough. The functions changing the size of the bucket table are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow) |
| shared upper_fill_ratio: FLT := 1.000; |
|---|
| **** | For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.) |
| shared upper_fill_ratio: FLT := 1.000; |
|---|
| **** | For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.) |